package com.lw.leetcode.tree.b;

import com.lw.leetcode.tree.TreeNode;

/**
 * 669. 修剪二叉搜索树
 *
 * @Author liw
 * @Date 2021/5/12 10:53
 * @Version 1.0
 */
public class TrimBST {

    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) {
            return root;
        }
        int val = root.val;
        if (val < low) {
            return trimBST(root.right, low, high);
        }
        if (val > high) {
            return trimBST(root.left, low, high);
        }
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;
    }

    public TreeNode trimBST2(TreeNode root, int low, int high) {
        TreeNode item = root;
        while (item != null) {
            int val = item.val;
            if (val >= low && val <= high) {
                break;
            }
            if (val < low) {
                item = item.right;
            }
            if (val > high) {
                item = item.left;
            }
        }
        if (item != null) {
            findMin(item.left, item, low);
            findMax(item.right, item, high);
        }
        return item;
    }

    private void findMax(TreeNode node, TreeNode last, int value) {
        if (node == null) {
            last.right = null;
            return;
        }
        if (node.val == value) {
            last.right = node;
            node.right = null;
        } else if (node.val > value) {
            findMin(node.left, last, value);
        } else {
            last.right = node;
            findMin(node.right, node, value);
        }
    }

    private void findMin(TreeNode node, TreeNode last, int value) {
        if (node == null) {
            last.left = null;
            return;
        }
        if (node.val == value) {
            last.left = node;
            node.left = null;
        } else if (node.val < value) {
            findMin(node.right, last, value);
        } else {
            last.left = node;
            findMin(node.left, node, value);
        }
    }


}
